package com.cqs.leetcode.link;

import com.cqs.leetcode.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * @author lixw
 * @date 2020/2/29 9:01
 */
public class LinkedListCycle142 {

    /***
     * 有环的话 遍历链表结束前结点会重复出现
     * 时间复杂度 O(N)
     * 空间复杂度 O(N)
     *
     * 题目要求返回的是环首个结点，若不存在返回空
     *
     */
    static public class Solution {
        public ListNode detectCycle(ListNode head) {
            Set<ListNode> exists = new HashSet<>();
            while (head != null) {
                if (exists.contains(head)) {
                    return head;
                }
                exists.add(head);
                head = head.next;
            }
            return null;
        }
    }

    static class Solution2 {
        public ListNode detectCycle(ListNode head) {
            //没有环
            if (head == null || head.next == null) return null;
            ListNode slow = head, fast = head.next;
            while (fast != null) {
                //第一次相遇
                if (fast == slow) {
                    break;
                }
                slow = slow.next;
                fast = fast.next;
                if (fast != null) {
                    fast = fast.next;
                }
            }
            //没有环
            if (fast != slow) {
                return null;
            }
            //1.fast走的距离一定是slow的两倍 => fast走的距离减一slow的距离一定是环周长的整数倍
            //2. 此时分别从快慢指针第一次相遇的位置的【下一个结点】和首地址同时，同频出发 首次相遇的位置就是"环首"

            //重要
            slow = slow.next;
            while (head != slow) {
                head = head.next;
                slow = slow.next;

            }
            return slow;
        }
    }

    public static void main(String[] args) {
        int[] init = {3, 2, 0, -4};

        ListNode node = new ListNode(init[0]), head = node;
        for (int i = 1; i < init.length; i++) {
            node.next = new ListNode(init[i]);
            node = node.next;
        }
        //
        node.next = head.next;
//        Solution solution = new Solution();
        Solution2 solution = new Solution2();
        long start = System.currentTimeMillis();
        ListNode result = solution.detectCycle(head);
        long end = System.currentTimeMillis();
        System.out.println("runTime(millionSeconds):" + (end - start));
        System.out.println(result == null ? null : result.val);

    }

}
